package mo.offer_version2;

import mo.common.TreeNode;

public class L07 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        return doBuild(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    private TreeNode doBuild(int[] preorder, int pfrom, int pto, int[] inorder, int ifrom, int ito) {
        TreeNode root = new TreeNode(preorder[pfrom]);
        int rootIndex = 0;
        for (int i = ifrom; i <= ito; i++) {
            if (inorder[i] == preorder[pfrom]) {
                rootIndex = i;
                break;
            }
        }
        int leftLength = rootIndex - ifrom;
        if (leftLength > 0) {
            root.left = doBuild(preorder, pfrom+1, pfrom + leftLength, inorder, ifrom, rootIndex-1);
        }
        if (ito - rootIndex > 0) {
            root.right = doBuild(preorder, pfrom+leftLength+1, pto, inorder, rootIndex+1, ito);
        }
        return root;
    }

    public static void main(String[] args) {
        L07 test = new L07();
        TreeNode root = test.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println(root);
    }

}
